﻿package utils
{
	public class PicturesMatching 
	{
		private var _mapArray:Array;
		private var columns:uint;//x_max
		private var rows:uint;//y_max
		private var type:Array;
		
		
		public function PicturesMatching():void
		{
			_mapArray = null;
		}
		
		public function set mapArray(_value:Array):void 
		{
			_mapArray = _value;
			columns = 0;
			rows = 0;
			try
			{
				columns = _mapArray.length;
				rows = _mapArray[0].length;
			}
			catch(e:Error){}
			getType();
		}
		
		public function get mapArray():Array 
		{
			return _mapArray;
		}
		private function getType():void
		{
			type = new Array();
			for(var i:uint = 0;i<columns;i++)
			{
				for(var j:uint = 0;j<rows;j++)
				{
					type[String(_mapArray[i][j].type)] = "Message";
				}
			}
		}
		/**
		 * 
		 * 提示的数列单元格
		 *  
		 **/
		public function getMatching():Array
		{
			for( var i:String in type)
			{			
				if(i == "-1")continue;
				var typepictureArray:Array = getTypepictureArray(i);
				if(!typepictureArray)continue;
				for(var k:uint = 0;k<typepictureArray.length;k++)
				{
					for(var j:uint = 0;j<typepictureArray.length;j++)
					{
						if(k==j)continue;
						var p:Array = getBestPath(typepictureArray[k],typepictureArray[j],true);
						if(p)return [typepictureArray[k],typepictureArray[j]];
					}
				}
				
			}
			return null;
		}
		/**
		 * 
		 * 得到满足条件的单元格
		 *  
		 **/
		private function getTypepictureArray(_type:String):Array
		{
			var __ceilArray:Array = new Array();
			for(var x_:uint = 0;x_<columns;x_++)
			{
				for(var y_:uint = 0;y_<rows;y_++)
				{
					if(_mapArray[x_][y_].type == _type && checkNeighbor([x_,y_],_type))__ceilArray.push([x_,y_]);
				}
			}
			return __ceilArray.length>0?__ceilArray:null;
		}
		/**
		 * 
		 * 筛选type为_type的有相邻的  或者周围有空白的——type为-1的；
		 *  
		 **/
		private function checkNeighbor(arr:Array,_type:String):Boolean
		{
			if(_mapArray[arr[0]][arr[1]-1].type == -1 || _mapArray[arr[0]][arr[1]-1].type == _type)return true;
			if(_mapArray[arr[0]+1][arr[1]].type == -1 || _mapArray[arr[0]+1][arr[1]].type == _type)return true;
			if(_mapArray[arr[0]][arr[1]+1].type == -1 || _mapArray[arr[0]][arr[1]+1].type == _type)return true;
			if(_mapArray[arr[0]-1][arr[1]].type == -1 || _mapArray[arr[0]-1][arr[1]].type == _type)return true;
			return false;
		}
		/**
		 * 
		 * 得到最佳路径
		 *  
		 **/
		public function getBestPath(arrA:Array,arrB:Array,test:Boolean=false):Array 
		{
			var a:Object = _mapArray[arrA[0]][arrA[1]];
			var b:Object = _mapArray[arrB[0]][arrB[1]];
			if(!_mapArray)return null;
			if (a.type != b.type)return null;
			if (a.x == b.x && a.y == b.y)return null;
			var path:Array = new Array();//返回的路径
			var t1:uint,t2:uint,v:int;
			var _p:Array;
			//横
			for (var x_:uint=0; x_<columns; x_++)
			{
				_p = new Array();
				//循环A
				v = x_ < a.x?-1:1;
				t1 = a.x;
				t2 = x_;
				for (; t1 != t2; t1 += v) 
				{
					_p.push([t1,a.y]);
					//trace("横A",[t1,a.y]);
					
				}				
				//循环A2B
				v = a.y < b.y?1:-1;
				t1 = a.y;
				t2 = b.y;
				for (; t1 != t2; t1 += v)
				{
					_p.push([x_,t1]);
					//trace("横A2B",[x_,t1]);
				}				
				//循环B
				v = x_ < b.x?1:-1;
				t1 = x_;
				t2 = b.x;
				for (; t1 != t2; t1 += v) 
				{
					_p.push([t1,b.y]);
					//trace("横B",[t1,b.y]);
				}				
				_p.shift();
				path.push(_p);
			}
			//竖
			for (var y_:uint=0; y_<rows; y_++) 
			{
				_p = new Array();
				//循环A
				v = y_ < a.y?-1:1;
				t1 = a.y;
				t2 = y_;
				for (; t1 != t2; t1 += v) 
				{
					_p.push([a.x,t1]);
					//trace("竖A",[a.x,t1]);
				}
				//循环A2B
				v = a.x < b.x?1:-1;
				t1 = a.x;
				t2 = b.x;
				for (; t1 != t2; t1 += v)
				{
					_p.push([t1,y_]);
					//trace("竖A2B",[t1,y_]);
				}
				//循环B
				v = y_ < b.y?1:-1;
				t1 = y_;
				t2 = b.y;
				for (; t1 != t2; t1 += v) 
				{
					_p.push([b.x,t1]);
					//trace("竖B",[b.x,t1]);
				}
				_p.shift();
				path.push(_p);
			}
			//path长度为columns+rows  也就是有这么多条可选路径
			//trace("1",path);
			path = path.filter(pathFilter);
			//trace("2",path);
			
			if (path.length > 0)
			{
				path.sort(pathSort);
				if(!test)
				{
					a.type = -1;
					b.type = -1;
				}
				//trace("FINISH PATH:",path[0]);
				return path[0];
			} 
			else 
			{
				return null;
			}
		}
		/**
		 * 
		 * 从columns+rows条路径中选出所有通路
		 *  
		 **/
		private function pathFilter(a:Array,b:uint,c:Array):Boolean 
		{					
			for (var i:uint = 0; i<a.length; i++) 
			{
				if (_mapArray[a[i][0]][a[i][1]].type != -1) 
				{
					return false;
				}
			}
			return true;
		}
		/**
		 * 
		 * 从所有通路中选出最短路径
		 *  
		 **/
		private function pathSort(a:Array,b:Array):int 
		{
			return a.length < b.length?-1:1;
		}

	}
}